#双亲表示法

class PTree:
    '''使用 “双亲表示法” 来存储和表示多叉树'''
    class PTNode:
        def __init__(self, val, parent=-1):
            self.value = val  # 节点的数据域
            self.parent = parent  # 表示节点的父节点的下标。根节点的parent = -1
        def __str__(self):
            return f'PTNode:{self.value}'

    def __init__(self):
        self.data = []
    def __str__(self):
        lst=[i.value for i in self.data]
        return f'PTree:{lst}'

    def add(self, data, parent):
        '''添加节点'''
        node = self.PTNode(data, parent)

        if parent == -1:  # 要添加根节点
            if not self.data:  # 为空树
                self.data.append(node)
            else: raise '树已经有根节点了，不能再添加节点'
        else:
            try: self.data.append(node)
            except IndexError as e:
                raise '节点的父节点不存在，非法插入'

    def parent(self, node):
        '''获取节点的父节点'''
        flag = False  # 要查询的节点 node 是否在树中
        for item in self.data:
            if item.value == node.value and item.parent == node.parent:
                flag = True
                break
        if not flag:
            raise '节点不存在'
        if node.parent == -1:
            print(f'Info: 节点{node}是根节点，它没有父节点')
            return None
        else:
            return self.data[node.parent]            

    def children(self, node):
        '''获取节点的所有子节点'''
        flag = False
        node_index = None  # 如果要查询的节点 node 在树中，它的下标是多少
        for item in self.data:
            if item.value == node.value and item.parent == node.parent:
                flag = True
                node_index = self.data.index(item)
                break
        if not flag:
            raise '节点不存在'
        # 再次遍历整棵树，判断每个节点的 parent 是否是 node 的下标
        return [child for child in self.data if child.parent == node_index]


if __name__ == '__main__':
    t = PTree()
    t.add('A', -1)
    t.add('B', 0)
    t.add('C', 0)
    t.add('D', 1)
    t.add('E', 2)
    t.add('F', 2)
    t.add('G', 3)
    t.add('H', 3)
    t.add('I', 3)
    t.add('J', 4)

    print(t)

    node = PTree.PTNode('B', 0)
    p=t.parent(node)
    print(p)

    node = PTree.PTNode('D', 1)
    c=t.children(node)
    print([i.value for i in c])